package com.aqie.medium.heap;

import java.util.Arrays;

/**
 * 313 超级丑数 : 所有质因数都是长度为 k 的质数列表 primes 中的正整数 todo
 */
public class NthSuperUglyNumber {
    /**
     * 1, 动态规划 33ms
     * @param n
     * @param primes
     * @return
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] idxs = new int[primes.length],dp = new int[n];//dp[i]由min{primes[j] * dp[idxs[j]]},j=[0,n)得到
        int i = 1;
        dp[0] = 1;
        while(i < n){
            int j = 0,min = Integer.MAX_VALUE;
            for(int num:primes){
                if(num * dp[idxs[j]] < min) min = num * dp[idxs[j]];
                j++;
            }
            dp[i] = min;
            j = 0;
            for(int num:primes){
                if(min == num * dp[idxs[j]]) idxs[j]++;
                j++;
            }
            i++;
        }
        return dp[dp.length - 1];
    }

    /**
     * 2, primes.length组序列，每次取竖向最小值，取到最小值的这个序列指针向前，将指针对应的值乘当前因子
     *  26ms
     */
    public int nthSuperUglyNumber2(int n, int[] primes) {
        int[] initPrimes = Arrays.copyOf(primes, primes.length);
        int[] primesIndexs = new int[primes.length];
        int[] results = new int[n];
        results[0] = 1;
        int i = 1;
        while(i < n) {
            int min = Integer.MAX_VALUE;
            for(int var : initPrimes) {
                if(var < min)
                    min = var;
            }
            results[i++] = min;
            for(int j = 0; j < initPrimes.length; j++) {
                if(min == initPrimes[j]) {
                    primesIndexs[j]++;
                    initPrimes[j] = results[primesIndexs[j]]*primes[j];
                }
            }
        }
        return results[n - 1];
    }
}
